package leetcode._203;

class Solution3 {

	public ListNode removeElements(ListNode head, int val) {
		// 最小问题就是链表只有一个null，此时处理这个链表（删除val），对于一个null来说，没有val，所以返回null
		if (head == null)
			return null;
		// removeElements(head.next, val)解决了一个更小的问题，就是head.next的更小的链表
		// 返回的结构就是res, res已经是处理完成的一个更小的链表
		ListNode res = removeElements(head.next, val);
		// 解决当前head
		if (head.val == val) {
			return res; // 抛弃当前head
		} else {
			head.next = res; // 接上那个更小的链表
			return head;
		}
	}

	public ListNode _removeElements(ListNode head, int val) {
		if (head == null)
			return null;

		head.next = _removeElements(head.next, val);
		return head.val == val ? head.next : head;
	}

	public ListNode _debugRemoveElements(ListNode head, int val, int depth) {
		String depthString = generateDepthString(depth);
		System.out.print(depthString);
		System.out.println("Call: remove " + val + " in " + head);

		if (head == null) {
			System.out.print(depthString);
			System.out.println("Return: " + head);
			return null;
		}

		ListNode res = _debugRemoveElements(head.next, val, depth + 1);
		System.out.print(depthString);
		System.out.println("After remove " + val + ": " + res);

		ListNode ret;
		if (head.val == val) {
			ret = res;
		} else {
			head.next = res;
			ret = head;
		}
		System.out.print(depthString);
		System.out.println("Return: " + ret);

		return ret;
	}

	private String generateDepthString(int depth) {
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < depth; i++)
			sb.append("--");
		return sb.toString();
	}

	public static void main(String[] args) {
		int[] arr = { 1, 2, 6, 3, 4, 5, 6 };
		ListNode head = new ListNode(arr);
		System.out.println(head);

//		System.out.println(new Solution3()._removeElements(head, 6));
		System.out.println(new Solution3()._debugRemoveElements(head, 6, 0));
	}

}
